/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-02-20
 * Time: 18:36
 */

//简单实现一下哈希-put 和 get方法
public class HashBucket {
    //hash容器
    static class Node {
        public int key;
        public String val;
        public Node next;

        public Node(int key, String val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] array;
    public int usedSize;//初始为0

    //负载因子一般严格控制在0.7-0.8以下（负载因子 = 填入表中元素个数/散列表长度）
    public static final double LOAD_FACTOR = 0.75;

    //初始化hash桶
    public HashBucket() {
        array = new Node[10];
    }

    //放元素
    public void put(int key, String val) {
        //找到对应hash桶下标
        int index = key % array.length;

        Node cur = array[index];
        //判断是否已经存在key值
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //采用头插法
        Node newNode = new Node(key, val);
        newNode.next = array[index];
        array[index] = newNode;
        usedSize++;

        //为减少冲突率，我们要判断负载因子是否超过预设值
        if (calculate_LoadFactor() >= LOAD_FACTOR) {
            //如果大于等于负载因子，需要扩容
            resize();
        }

    }

    //扩容
    private void resize() {
        //扩容
        Node[] newArray = new Node[array.length * 2];
        //因为改变了散列表长度，需要重新将每一个结点散列到新的位置
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                //记录curNext的位置，防止后续调整丢失
                Node curNext = cur.next;
                //头插法
                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }

    //计算此时负载因子
    private double calculate_LoadFactor() {
        return usedSize * 1.0 / array.length;
    }

    //取元素
    public String get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}
